package algorithm.middle;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
 * <p>
 * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
 * <p>
 * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindMinArrowShots452 {

    /**
     * 贪心
     * 排序points数组，从后往前遍历。选取最后一个区间最小的元素，如果与前面区间有交集，则跳过。若没有交集，则取前一个区间的最小值继续遍历匹配。
     * [1,6],[2,8],[7,12],[10,16]
     * 10->2
     */
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt(o -> o[0]));
        int co = points[points.length - 1][0];
        int res = 1;
        for (int i = points.length - 2; i > -1; i--) {
            if (points[i][0] <= co && points[i][1] >= co) {
                continue;
            }
            co = points[i][0];
            res++;
        }
        return res;
    }

    public static void main(String[] args) {
        new FindMinArrowShots452().intersectionSizeTwo(new int[][]{{1, 2}, {2, 3}, {2, 4}, {4, 5}});
    }


    /**
     * 交集大小至少为2个，相同思路
     *
     * @param intervals
     * @return
     */
    public int intersectionSizeTwo(int[][] intervals) {
        //[a,b] a升序，b降序。这样遍历的时候，能快速把区间[a,b]中较小的元素进行替换。
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0]==o2[0]) return o2[1] - o1[1];
            return o1[0] - o2[0];
        });
        int lower = intervals[intervals.length - 1][0];
        int higher = lower + 1;
        int res = 2;
        for (int i = intervals.length - 2; i > -1; i--) {
            //两个元素都在区间内
            if (intervals[i][0] <= higher && intervals[i][1] >= higher) {
                continue;
            }
            //只有lower在区间内，进行替换
            if (intervals[i][0] <= lower && intervals[i][1] >= lower) {
                higher = lower;
                lower = intervals[i][0];
                res++;
                continue;
            }
            lower = intervals[i][0];
            higher = lower + 1;
            res += 2;
        }
        return res;
    }

}
